package StackAndQueue;

import java.util.*;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class topKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

//        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
//        // 使用Collections.sort()方法并传递自定义比较器来排序
//        list.sort((o1, o2) -> o2.getValue().compareTo(o1.getValue()));
//        List<Integer> result = new ArrayList<>();
//        for (Map.Entry<Integer, Integer> entry : list) {
//            result.add(entry.getKey());
//        }
//        return result.subList(0, k).stream().mapToInt(Integer::intValue).toArray();
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(pq.size() < k){
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]){
                    pq.poll();
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}